package com.zhugang.week13.sorting;

/**
 * @program algorithms
 * @description: selectionSort
 * @author: chanzhugang
 * @create: 2022/09/30 22:24
 */
public class SelectionSort implements IMutableSorter {

    /**
     * 选择排序：选择最大的值放在最后面(从后往前排序)
     * O(n^2)
     *
     * @param A
     */
    @Override
    public void sort(int[] A) {
        for (int i = A.length - 1; i >= 0; i--) {
            // 最大值下标
            int j = maxIndex(A, 0, i + 1);
            // 交换最大值放到最后面
            swap(A, i, j);
        }
    }

    private int maxIndex(int[] A, int i, int j) {
        // i - j 中找最大值的下标
        int maxValue = Integer.MIN_VALUE;
        int maxIndex = i;
        while (i < j) {
            if (A[i] > maxValue) {
                // 更新最大值、最大值下标
                maxValue = A[i];
                maxIndex = i;
            }
            i++;
        }
        return maxIndex;
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}